package class5;

import common.TreeNode;
import common.TreeNodeUtils;

/**
 * https://leetcode.cn/problems/validate-binary-search-tree/description/
 * 搜索二叉树
 * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
 *
 * 有效 二叉搜索树定义如下：
 * 节点的左子树 只包含 小于 当前节点的数。
 * 节点的右子树 只包含 大于 当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。
 *
 * 解题思路：
 * 1.左树是否为搜索二叉树、右树书否为搜索二叉树
 * 2.当前节点 大于左边的max值，小于右边节点的min值
 * ----------------------------------------
 */
public class Code08_isBinarySearchTree {

    public static void main(String[] args) {

        TreeNode treeNode1 = TreeNodeUtils.getBinarySearchTree();
        Boolean binarySearchTree = isBinarySearchTree(treeNode1);
        System.out.println("binarySearchTree = " + binarySearchTree);
    }

    public static Boolean isBinarySearchTree(TreeNode root) {
        return process(root).BST;
    }

    public static class Info {
        public boolean BST;
        public int max;
        public int min;

        public Info(boolean BST, int max, int min) {
            this.BST = BST;
            this.max = max;
            this.min = min;
        }
    }


    public static Info process(TreeNode x) {
        if (x == null) {
            return null;
        }
        Info left = process(x.left);
        Info right = process(x.right);
        int max = x.val;
        int min = x.val;
        // 获取左树和右树的最大直和最小值
        if (left != null) {
            max = Math.max(left.max, max);
            min = Math.min(left.min, min);
        }
        if (right != null) {
            max = Math.max(right.max, max);
            min = Math.min(right.min, min);
        }

        boolean isBst = true;
        // 如果左树或右树不是搜索二叉树，则就不是搜索二叉树
        if (left != null && !left.BST) {
            isBst = false;
        }
        if (right != null && !right.BST) {
            isBst = false;
        }

        // left.max < x &&  right.min > x
        boolean leftMaxLessX = left == null ? true : (left.max < x.val);
        boolean rightMinMoreX = right == null ? true : (right.min > x.val);
        // 如果其中一个不成立，则整个树就都不成立
        if (!leftMaxLessX || !rightMinMoreX) {
            isBst = false;
        }

        return new Info(isBst, max, min);
    }


}


